|
In numerical analysis, the Kahan summation algorithm (also known as compensated summation 〔Strictly, there exist other variants of compensated summation as well: see 〕) significantly reduces the numerical error in the total obtained by adding a sequence of finite precision floating point numbers, compared to the obvious approach. This is done by keeping a separate ''running compensation'' (a variable to accumulate small errors). In particular, simply summing ''n'' numbers in sequence has a worst-case error that grows proportional to ''n'', and a root mean square error that grows as for random inputs (the roundoff errors form a random walk). With compensated summation, the worst-case error bound is independent of ''n'', so a large number of values can be summed with an error that only depends on the floating-point precision.〔 The algorithm is attributed to William Kahan.〔 〕 Similar, earlier techniques are, for example, Bresenham's line algorithm, keeping track of the accumulated error in integer operations (although first documented around the same time〔Jack E. Bresenham, ("Algorithm for computer control of a digital plotter" ), ''IBM Systems Journal'', Vol. 4, No.1, January 1965, pp. 25–30〕) and the Delta-sigma modulation〔H. Inose, Y. Yasuda, J. Murakami, "A Telemetering System by Code Manipulation – ΔΣ Modulation," IRE Trans on Space Electronics and Telemetry, Sep. 1962, pp. 204–209.〕 (integrating, not just summing the error). ==The algorithm== In pseudocode, the algorithm is: function KahanSum(input) var sum = 0.0 var y,t // Temporary values. var c = 0.0 // A running compensation for lost low-order bits. for i = 1 to input.length do y = input() - c // So far, so good: ''c'' is zero. t = sum + y // Alas, ''sum'' is big, ''y'' small, so low-order digits of ''y'' are lost. c = (t - sum) - y // ''(t - sum)'' recovers the high-order part of ''y''; subtracting ''y'' recovers -(low part of ''y'') sum = t // Algebraically, ''c'' should always be zero. Beware overly-aggressive optimizing compilers! next i // Next time around, the lost low part will be added to ''y'' in a fresh attempt. return sum 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kahan summation algorithm」の詳細全文を読む スポンサード リンク
|